package com.xiaoyu.graph;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;

/**
 * @program: DS_and_A
 * @description: TODO
 * @author: YuWenYi
 * @create: 2021-05-17 09:50
 **/
public class Graph {

    public static void main(String[] args) {
        Graph graph = new Graph(8);
        graph.addVertex("A");
        graph.addVertex("B");
        graph.addVertex("C");
        graph.addVertex("D");
        graph.addVertex("E");
        graph.addVertex("F");
        graph.addVertex("G");
        graph.addVertex("H");

        graph.addEdge(0,1,1);
        graph.addEdge(0,2,1);
        graph.addEdge(1,3,1);
        graph.addEdge(1,4,1);
        graph.addEdge(3,7,1);
        graph.addEdge(4,7,1);
        graph.addEdge(2,5,1);
        graph.addEdge(5,6,1);
        graph.showGraph();

        System.out.println("===============");

        graph.DFS();
    }

    private ArrayList<String> vertexList;  //存储图中所有的顶点

    private int[][] edges;  //存储图的链接矩阵

    private int edgesNums;  //记录图中边的数量

    private boolean[] visited;  //遍历时,用来记录某结点是否已经被访问过

    public Graph(int vertexNums) {
        edges = new int[vertexNums][vertexNums];
        vertexList = new ArrayList<>(vertexNums);

        visited = new boolean[vertexNums];
    }

    //添加一个顶点
    public void addVertex(String vertex){
        vertexList.add(vertex);
    }

    //在邻接矩阵中添加一条边
    public void addEdge(int v1Index,int v2Index,int weight){
        edges[v1Index][v2Index] = weight;  //使用无向图,因此坐标对称
        edges[v2Index][v1Index] = weight;
        edgesNums++;
    }

    //得到第一个邻接结点在集合中的下标,如果没找到就返回-1
    public int getFirstNeighbor(int currentVertexIndex){
        for (int i = 0; i < vertexList.size(); i++) {
            if (edges[currentVertexIndex][i] > 0)  //currentVertexIndex即当前正在深度遍历的那行的结点
                return i;
        }
        return -1;
    }

    //假设正在深度遍历结点B,此时C遍历完成回到B,此时要如何得到B后面的D?,那么就需要根据结点B和C,来获取D
    public int getNextNeighbor(int currentVertexIndex,int visitedIndex){
        //从结点C开始,往后找,前面的不用找了已经遍历完了
        for (int i = visitedIndex + 1; i < getVertexSize(); i++) {
            if (edges[currentVertexIndex][i] > 0)
                return i;
        }
        return -1;
    }

    //对某一个结点进行深度优先遍历算法,注意,这里只能对你给定的结点进行深度优先遍历,因此还不够
    //因为仅仅对某一个结点进行DFS,那么也许该结点的DFS并不能完全包含所有的结点,因此要对每一个上层结点进行DFS!
    //简单来说,一次这样的遍历,这样遍历一个连通图,而一旦图中有多个连通图,那么就无法使用它来一次遍历成功了
    private void DFS(boolean[] visited,int vertexIndex){
        //访问当前结点
        System.out.print(getVertexValueByIndex(vertexIndex)+" ");
        //将该结点的是否访问设置成已访问
        visited[vertexIndex] = true;
        //获取当前结点的第一个邻接点w
        int w = getFirstNeighbor(vertexIndex);

        while (w != -1){
            //如果还没有被访问,那么就进行深度优先遍历
            if (!visited[w]){
                DFS(visited,w);
            }
            //在当前的结点行,并且已经访问过的结点w处,找到下一个邻接点
            w = getNextNeighbor(vertexIndex,w);
        }
    }

    //对每一个结点都进行深度优先遍历,因为图有非连通图的情况!!,因此就必须对每个结点进行DFS
    public void DFS(){
        //类似于回溯,此时回溯到最上层,继续访问最上层的下一个结点
        for (int i = 0; i < getVertexSize(); i++) {
            //如果该结点没有访问过
            if (!visited[i]){
                DFS(visited,i);
            }
        }
    }


    //对某个结点进行广度优先遍历BFS
    private void BFS(boolean[] visited,int vertexIndex){
        int u; //表示队列的头结点对应的下标
        int w; //表示邻接结点w
        //用来记录结点访问的顺序
        LinkedList<Integer> queue = new LinkedList<>();
        //访问该结点,输出结点信息
        System.out.print(getVertexValueByIndex(vertexIndex)+ " ");
        //将该结点的是否访问设置成已访问
        visited[vertexIndex] = true;
        //将已访问的结点加入队列中
        queue.offer(vertexIndex);
        while (!queue.isEmpty()){  //队列为空时,就完成了一个连通图的广度优先遍历
            //取出队列的头结点,即最早被访问的结点
            u = queue.poll();
            //获取u的第一个邻接结点的下标
            w = getFirstNeighbor(u);
            while (w != -1){  //说明找到了邻接结点  -->这个循环每次都会访问该结点行的所有邻接结点
                if (!visited[w]){  //如果该还没被访问,则去访问它
                    System.out.print(getVertexValueByIndex(w)+ " ");
                    visited[w] = true;
                    queue.offer(w);
                }
                //获取邻接矩阵中结点u的那行(link),以结点w开始,查找u那行是否有下一个邻接点
                w = getNextNeighbor(u,w);  //这里就可以体现出BFS,是一行行的找,而不是往深度里面挖
            }
        }
    }
    //与DFS类似,上面的算法一次性只能访问一个连通图,如果图中有多个连通图,就需要进行遍历依次进行广度优先遍历
    public void BFS(){
        for (int i = 0; i < getVertexSize(); i++) {
            //如果该结点没有访问过
            if (!visited[i]){
                BFS(visited,i);
            }
        }
    }

    //返回结点的数量
    public int getVertexSize(){
        return vertexList.size();
    }

    //返回边的数量
    public int getEdgesNums(){
        return edgesNums;
    }

    //返回邻接矩阵中下标i的对应顶点
    public String getVertexValueByIndex(int i){
        return vertexList.get(i);
    }

    //返回指定坐标下v1和v2之间的权值
    public int getWeight(int v1Index,int v2Index){
        return edges[v1Index][v2Index];
    }

    //将图对应的邻接矩阵给打印出来
    public void showGraph(){
        boolean flag = true;
        int i = 0;
        for (int[] row : edges) {
            if (flag){
                for (String vertex : vertexList) {
                    System.out.print("  "+vertex);
                }
                System.out.println();
                flag = false;
            }
            System.out.print(vertexList.get(i++));
            System.out.println(Arrays.toString(row));
        }
    }

}
